package org.example.myleet.p764;

public class Solution {

    private static final int VAL = 0;
    private static final int LEFT = 1;
    private static final int UP = 2;
    private static final int RIGHT = 3;
    private static final int DOWN = 4;

    public int orderOfLargestPlusSign(int n, int[][] mines) {
        int max = 0;
        //0-val, 1-left, 2-up, 3-right, 4-down
        int[][][] dp = new int[n][n][5];
        //标记所有的mine
        for (int[] mine : mines) {
            dp[mine[0]][mine[1]][VAL] = 1;
        }
        //从左往右从上往下动态规划，求得每一个非mine的格子的左臂和上臂最大长度
        for (int r = 0; r < n; ++r) {
            int r_ = r - 1;
            for (int c = 0; c < n; ++c) {
                if (dp[r][c][VAL] == 1) {
                    continue;
                }
                int c_ = c - 1;
                if (c_ >= 0) {
                    dp[r][c][LEFT] = dp[r][c_][LEFT] + 1;
                } else {
                    dp[r][c][LEFT] = 1;
                }
                if (r_ >= 0) {
                    dp[r][c][UP] = dp[r_][c][UP] + 1;
                } else {
                    dp[r][c][UP] = 1;
                }
            }
        }
        //从右往左从下往上动态规划，求得每一个非mine的格子的右臂和下臂最大长度
        for (int r = n - 1; r >= 0; --r) {
            int r_ = r + 1;
            for (int c = n - 1; c >= 0; --c) {
                if (dp[r][c][VAL] == 1) {
                    continue;
                }
                int c_ = c + 1;
                if (c_ < n) {
                    dp[r][c][RIGHT] = dp[r][c_][RIGHT] + 1;
                } else {
                    dp[r][c][RIGHT] = 1;
                }
                if (r_ < n) {
                    dp[r][c][DOWN] = dp[r_][c][DOWN] + 1;
                } else {
                    dp[r][c][DOWN] = 1;
                }
                //上下左右都知道臂长的情况下取最小臂长就是该格子的十字符号的阶数，记录最大的
                int min = Math.min(dp[r][c][LEFT], dp[r][c][RIGHT]);
                min = Math.min(min, dp[r][c][UP]);
                min = Math.min(min, dp[r][c][DOWN]);
                max = Math.max(max, min);
            }
        }
        return max;
    }
}
